1. Field of the Invention
This invention relates generally to the field of integrated circuit design technology and more specifically to methodologies for routing the interconnections between components of an integrated circuit.
2. Background
Microelectronic integrated circuits (ICs) consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The physical design of an IC transforms an abstract circuit description into a geometric description, which is known as “layout” and which consists of a set of planar geometric shapes in several layers. The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield.
The physical design of a microelectronic IC commonly is an automated optimization process using digital computers and specialized Computer Aided Design (CAD) tools. Automation of the physical design process has increased the level of integration, reduced turn-around time and enhanced chip performance.
A generated layout has to be checked to ensure that it meets all of the design requirements. The result of this check is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called “masks” by an optical or electron beam pattern generator.
For the physical design of ICs, prefabricated elements are used that provide combinatorial or storage functions. These elements are called cells (or types). A collection of different cells forms a library. The usage of a cell in a design is referred to as instance or circuit. If most of cells have the same height and connect their power through abutted placement in circuit row, the cells are called standard cells and the design style standard cell layout.
A particular design element of an IC is a so-called “pin” which refers to a physical or logical access terminal to a cell and circuit. An example for a pin is an inverter having one input and one output pin.
The mentioned instances of an IC are interconnected or routed in accordance with the logical design of the circuit to provide the desired functionality. Hereby the various elements of the circuit are interconnected by electrically conductive lines or traces that are routed through vertical channels and horizontal channels that run between the cells.
The whole design process consists of the following three design phases namely Partitioning, Floor planning and placement, and Routing:
1. Partitioning—A chip may contain several million transistors and therefore the layout of the entire circuit cannot be handled in a reasonable amount of time using the currently available computation power. Therefore the layout is partitioned by grouping components into blocks such as sub circuits and modules. The output of partitioning is a set of blocks, along with the interconnections required between blocks. The set of interconnections and connected objects is referred to as a “netlist”.
2. Floor planning and placement—This step is concerned with selecting good layout alternatives for each block of the entire chip, as well as between blocks and to the edges. Floor planning is a critical step as it sets up the ground work for a good layout. During placement, the blocks are exactly positioned on the chip. The goal of placement is to find a minimum area arrangement for the blocks that allows completion of interconnections between the blocks in such a way that they obey technology constraints. The placement must be legal, i.e. have no overlaps and must meet e.g. technology constraints.
Placement is typically done in two phases. In the first phase, an initial placement is created. In the second phase, the initial placement is evaluated and iterative improvements are made until the layout has minimum area and conforms to design specifications.
3. Routing—The goal of a router is to complete all circuit connections while trying to use the shortest possible wire length. Routing is usually done in two phases referred to as “global routing” and “detailed routing” phases.
During the global routing, connections are completed between the proper blocks of the circuit disregarding the exact geometric details of each wire and terminal. For each wire, a global router finds a list of channels that are to be used as a passageway for that wire. In other words, global routing specifies the loose route of a wire through different regions of the routing space.
After the global routing, the global wires have to be legalized, namely by connecting them to off-grid contact pins and maybe by moving the global wires around off-grid areas that have to be blocked to prevent not allowed short circuits or other not allowed electrical connections of the underlying circuit layout (so-called “blocking areas”). However, this legalization step is rather complex and thus computationally extensive.
In addition, IC chips typically have several metal layers upon which the wires are routed with the horizontal wires routed on different layers than the vertical wires. An electrical connection between two nets on adjacent layers is implemented using a so-called “via” which is an etched hole in a substrate's oxide for allowing a conductive path to extend from one layer to another layer of the underlying IC chip, that can be used e.g. for conducting power (so-called “power via”) or even signals. The routing program must therefore produce a list of horizontal and vertical segments for each net, connected by the mentioned vias, all of which have to be conformal with the underlying technology requirements, also known as ‘ground rules’, for wire spacing and wire capacity.
Since the placement process may produce a non-routable layout, the chip might need to be replaced or re-partitioned before another routing is attempted. The whole design cycle is conventionally repeated several times to accomplish the design objectives. The complexity of each step varies depending on the design constraints as well as the design style used.
For the above mentioned wiring (i.e. designing the electrical connections between the blocks) it is well-known to utilize so-called ‘Gridded Routers’. The basic aspects of grid-based routing are described in a white paper of Cadence Design Systems, Inc., San Jose, Calif., USA published in 2004 and entitled “Routing Requirements for the Nanometer Era”.
Grid-based routers superimpose a virtual ‘mesh’-like template (the so-called “routing grid” or “wiring grid”) over the routing area of the design with evenly spaced tracks, or grids, running both vertically and horizontally across the design area. Every vertical and horizontal grid intersection point on the mesh is maintained as a pointer in the memory of an underlying computer, and any routing operation that is performed must be cognizant of all the grid points in the design as a whole and aware of any trade-offs, timing, congestion, design rule check (DRC), etc. involved with the specific operation before completing it. Most of the presently known routers are grid-based and only the pin-access is usually non-gridded. The reason is that a true gridless router would need a nearly infinite search space for possible wiring lines thus revealing huge run times even with small designs. On the other hand, in the case of grid-based routers, the larger the design grows or the smaller the process geometry or space between grid points becomes, the more grid points are needed to be allocated in memory, and therefore, the more time it will take for a gridded router to perform any task.
Further to the above mentioned white paper, in an article entitled “Routing for Complex SoC Designs” and being published by Synopsys, Inc., in 1999, the above described design planning and routing, including the mentioned floor planning, is disclosed in greater detail. This article, on page 5, includes a comparison of grid-based and non-grid-based routing algorithms.
In particular, in the field of Very Large-Scale Integrated (VLSI) circuit designs, in the past, the above mentioned gridded routers have been applied to circuit structures which are a multiple of a uniform grid and insofar fit into or match with the router's grid. However, recently developed chip technologies like the known Cu based 65 nm process technology require that only ground rules have to be considered. As a consequence, structures like contact pins or the above mentioned blocked or blocking areas are ‘gridless’ data and thus cannot be aligned with a simple routing grid. In addition, the grids for the above described placement and routing processes comprise differing offsets, i.e. these grids cannot be aligned with each other.
There exist prior art approaches (see above two citations) according to which the routing is accomplished on a gridless basis wherein interconnections are constructed without any geometrical restrictions. However, this gridless routing does not have the above described algorithmic advantages and is by a factor 4 slower than a grid-based approach.
Furthermore, the above described legalization step that is executed after the global routing, requires a computer-extensive calculation of the pin access of the contact pins and has to be executed for each single pin.
Although gridded routers are known for their relatively high speed, they lack the flexibility required for the above mentioned complex VLSI designs.
Another drawback of the grid-based routers (see above mentioned Cadence White Paper, Sec. 6.1.1) is that the position of the pre-described vias disadvantageously has to be fixed prior to the routing.